/*
 * This is written by Lulu Han.
 * E-mail: locomotive_crypto@163.com
 */

#include <vector>
#include "lcs.hpp"

LCS::LCS(const std::string& str1, const std::string& str2){
	m_str1 = str1;
	m_str2 = str2;
}

int LCS::length(){
	int str1_len = m_str1.length();
	int str2_len = m_str2.length();
	
	// Generate a (str1_len+1)*(str2_len+1) matrix M
	std::vector< std::vector<int> > M;
	for(int i = 0; i < str1_len + 1; ++i){
		std::vector<int> m;
		m.resize(str2_len+1);
		
		M.push_back(m);
	}
	
	// Initialize the matrix M
	for(int i = 0; i < str1_len + 1; ++i){
		for (int j = 0; j < str2_len + 1; ++j){
			if( i == 0 || j == 0)
				M[i][j] = 0;
		}
	}

	// Compute the length of LCS
	for(int i = 1; i < str1_len + 1; ++i){
		for (int j = 1; j < str2_len + 1; ++j){
			if (m_str1[i-1] == m_str2[j-1])
				M[i][j] = M[i-1][j-1] + 1;
			else
				M[i][j] = std::max(M[i][j-1], M[i-1][j]);
		}
	}
	return M[str1_len][str2_len];
}
